home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Light ROM 1
/
LIGHT-ROM 1 (Amiga Library Services)(1994).iso
/
ffdisks
/
d926.lha
/
TreeTool
/
TreeTool.doc
< prev
next >
Wrap
Text File
|
1993-10-07
|
8KB
|
255 lines
TreeTool link library 1.0 (Public Domain).
------------------------------------------
Jean-Christophe Clement, Summer 1993.
Introduction:
This library implements some functions to make working with acyclic, n-ary
tree a breeze. This documentation will give you some information on how to
use it but will assume some working knowledge of tree concept and, of
course, a good understanding of 'C'. Some example of usage are given at
end of this file.
Some background:
I designed this library mainly for a project I was working on at
University of Sherbrooke and, after looking in the Fish disk lib, I found
that no generic tool like this one was available for the Amiga. It's not
that it is very hard or long to code (It took me less than a day to do so)
but it is done and tested (The project was relying heavily on TreeTool) so
you can use it and work on more important problem in you own code. By the
way, the 'C' code is VERY portable and can be used with any ANSI C
compiler (my project was running on Unix). No special consideration on
performance issue has been given other than the double-link on the child
list.
The Aplication Programmer Interface (API):
I took several "object-oriented" approach when designing TreeTool and
I think it reflects in the API. These are: data abstraction, information
hiding and methods. Of course, it means that, to make an usefull use of the
TreeTool lib, you must use ONLY the supplied function to acces the tree
structure.
Available functions are:
NODE_HANDLE tt_NewNode(NODE_HANDLE nodeHandle,void *data);
void tt_KillNode(NODE_HANDLE nodeHandle,void (*killFunc)() );
NODE_HANDLE tt_GetLeftBrother(NODE_HANDLE nodeHandle);
NODE_HANDLE tt_GetRightBrother(NODE_HANDLE nodeHandle);
void tt_GetSuperMariosBrother();
NODE_HANDLE tt_GetFirstSon(NODE_HANDLE nodeHandle);
NODE_HANDLE tt_GetLastSon(NODE_HANDLE nodeHandle);
NODE_HANDLE tt_GetFather(NODE_HANDLE nodeHandle);
void * tt_SetNodeData(NODE_HANDLE nodeHandle,void *data);
void * tt_GetNodeData(NODE_HANDLE nodeHandle);
void tt_ApplyFunction(NODE_HANDLE nodeHandle, void (*oneFunc)());
tt_NewNode:
Function: Allocate memory for a new node. Will make the new
node a son of the NODE_HANDLE passed if a non-NULL value
is given. Pointer to user data passed is kept internally.
Note: If NULL is passed as 'nodeHandle', the function
will return a node linked to nothing (Be aware to
use it carefully). If NULL is passed as 'data', a
NULL data pointer will be put in the node but the
node will still be created.
Return NULL is no new node has been allocated (if
no memory is free for use). All the nodes created
must be deallocated with tt_KillNode().
tt_KillNode:
Function: Deallocate all the memory for the specified node
and all of it's child's node memory. Frees data
too using the passed function (of course, we
assume that the client will de-allocate the data
correctly!)
Note: Instead of keeping pointers to all of the allocated
node for an eventual deletion on quit, you can use
tt_KillNode on the root node. tt_KillNode will
recursively delete all of the nodes and will call
back your destruction function to free the contained
data at each node. Your call-back function must have
only one parameter, a data pointer, that will correspond
to the user data pointer of the node to be deleted.
You can pass a NULL function pointer as call-back, in
wich case nothing will be called.
tt_GetLeftBrother:
Function: Returns the left brother of the passed node if
they both exist.
Note: Returns NULL otherwise. In the current implementation,
the left brother access time is O(1).
tt_GetRightBrother:
Function: Returns the right brother of the passed node if
they both exist.
Note: Returns NULL otherwise. In the current implementation,
the right brother access time is O(1).
tt_GetSuperMariosBrother:
Function: To prove that there is still place for fun in
computer sciences.
Note: Is harmless actually.
tt_GetFirstSon:
Function: Returns the first left son of the specified node.
Note: Returns NULL is there is not such a son. In the current
implementation, the first son access is O(1).
tt_GetLastSon:
Function: Returns the rightmost son of the specified node.
Note: Returns NULL is there is no such son. Access time is O(n).
tt_GetFather:
Function: Returns the father node associated with the passed
one.
Note: NULL if at top of tree or a NULL NODE_HANDLE is passed.
At worst, access time is O(n).
tt_SetNodeData
Function: Will link the passed data pointer to the pased node.
Note: If there is already a data pointer in this node,
it will be replaced (you must destroy it first!).
Returns a void pointer where the client
can write to modify the node content
directly.
tt_ApplyFunction:
Function: Recursively apply a passed function on every node of the Tree
that is a child (sub-child, etc...) of NODE_HANDLE and
to NODE_HANDLE itself.
Note: Your call-back function will receive one
parameter which will be the NODE_HANDLE of the
current node you want your function to be used on.
Function will be applied on the prefix path.
Voila! let's hope everything is clear...
To compile your program using TreeTool, consult your compiler manual
on linking. See the example script for SAS/C.
To compile TreeTool using SAS/C (5.1 in my case), nothing more
than "lc -O treetool.c" is necessary.
Now, one example:
We construct a tree with a child that has one child itself, use them a
bit and kill the tree before quitting. This is quite straightforward, I
doubt anybody will need more info.
#include "TreeTool.h"
#include <stdio.h>
/* Some prototypes. */
void displayFunc(NODE_HANDLE);
void mkillFunc(struct someData *);
struct someData
{
int a,b,c;
char *string;
}
main()
{
NODE_HANDLE a_tree=NULL;
struct someData data1={1,2,3,"Root node."},data2,data3={7,8,9,"Sub-child node."};
struct someData *ptrDat2;
/* We create our tree root. */
a_tree=tt_NewNode(NULL,NULL);
/* Let's create a child. */
tt_NewNode(a_tree,&data2);
/* Create a child of the child. */
tt_NewNode(tt_GetFirstSon(a_tree),&data3);
/* Set the root node pointer. */
tt_SetNodeData(a_tree,&data1);
/* Get the user data pointer to the child node. */
ptrDat2=tt_GetNodeData(tt_GetFirstSon(a_tree));
/* We can now fill it with "meaningfull" information. */
if( ptrDat2 )
{
ptrDat2->a=4;
ptrDat2->b=5;
ptrDat2->c=6;
ptrDat2->string="Child node.";
}
/* We will use our displayFunc to recursively display the message */
/* in each node. */
tt_ApplyFunction(a_tree,displayFunc);
printf("\n");
/* We kill all the allocated nodes before quitting. */
/* We could just have used tt_KillNode(a_tree,NULL) because data is */
/* static. */
tt_KillNode(a_tree,mkillFunc);
}
void displayFunc(NODE_HANDLE node)
{
struct someData *ptrData;
if( ptrData=tt_GetNodeData(node) )
{
printf("This node contains the message: %s\n",ptrData->string);
}
}
void mkillFunc(struct someData *ptrData)
{
/* Actually does nothing but could do something if dynamic data was */
/* used. */
printf("Killing the node containing message: %s\n",ptrData->string);
}
The final word:
If you like it and use it, that's great!
If you want to contact me:
Jean-Christophe Clement
921 rang 3, St-Simon
Quebec, CANADA
J0H-1Y0
Internet: clemj00@dmi.usherb.ca